Prefikso-sufiksy

Limit pamięci: 32 MB

Prefikso-sufiksem danego słowa nazywamy słowo , które jest zarówno prefiksem (początkowym fragmentem), jak i sufiksem (końcowym fragmentem) . Prefikso-sufiksem właściwym jest każdy jego prefikso-sufiks, który jest niepusty i krótszy od . Niech oznacza liczbę właściwych prefikso-sufiksów słowa . Przez oznaczamy podsłowo słowa zaczynające się na pozycji i kończące się na pozycji . Pozycje numerujemy od .

Dane jest słowo . Twoim zadaniem jest wyznaczenie łącznej liczby właściwych prefikso-sufiksów wszystkich podsłów , czyli obliczenie wyrażenia

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się słowo , składające się z co najmniej i co najwyżej znaków. W słowie występują jedynie małe litery alfabetu angielskiego.

Wyjście

Na wyjściu należy wypisać sumaryczną liczbę właściwych prefikso-sufiksów wszystkich podsłów .

Przykład

Dla danych wejściowych:

ababa

poprawną odpowiedzią jest:

7

Autor zadania: Szymon Majewski.